﻿// 4078. 01串.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
https://www.acwing.com/problem/content/4081/

给定一个整数 k
。

现在，我们可以对 01
 字符串进行如下操作：

选择其中恰好 k
 个连续的 1
，将它们都变为 0
。

如果一个 01
 字符串可以通过若干次上述操作，变为一个全 0
 字符串，那么就称这个字符串很优秀。

本题共需要回答 T
 组询问，每组询问给定两个整数 l,r
，并请你计算长度在 [l,r]
 范围内的所有 01
 字符串中优秀字符串的数量。

输入格式
第一行包含两个整数 T
 和 k
。

接下来 T
 行，每行包含两个整数 l,r
。

输出格式
共 T
 行，第 i
 行输出第 i
 组询问的答案对 109+7
 取模后的结果。

数据范围
前三个测试点满足 1≤T,k≤10
。
所有测试点满足 1≤T,k≤105
，1≤l≤r≤105
。

输入样例：
3 2
1 3
2 3
4 4
输出样例：
6
5
5
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 